package bit_operation;

import java.util.HashMap;
import java.util.HashSet;

public class KM {

    /**
     * 一个数组中，有一种数字出现了k次，其他数都出现了m次， m > k ,
     * k > 1，如何找到，并打印出这两种数，要求时间复杂度O(n)额外空间复杂度O(1)？
     * 
     * @param arr
     *            给定的数组，数组中有一种数字出现了k次，
     *            其他数都出现了m次， M > K ,
     *            k > 1
     * @param k
     * @param m
     * @return return 0;
     */
    public static int onlyKTimes(int[] arr, int k, int m) {
        // 先准备一个大小为32的数组;
        int[] t = new int[32];
        // t[0] 0位置的1出现了几次;
        // t[1] 1位置的1出现了几次;
        // t[i] i位置的1出现了几次;
        // 内层for循环执行次数确定，所以时间复杂度仍然是O(n)
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                // 说明i位置上的数字是1
                // 等价于 t[i] += (num >> i) & 1;
                if (((num >> i) & 1) != 0) {
                    t[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            // t[i] % m != 0 在第i位上，有1
            // t[i] % m == k 说明这个数出现了k次
            if (t[i] % m == 0) {
                continue;
            }
            if (t[i] % m == k) {
                ans |= (1 << i);
            } else {
                return -1;
            }
        }
        // 可能存在ans为0的情况，所以需要判断
        if (ans == 0) {
            int count = 0;
            for (int num : arr) {
                if (num == 0) {
                    count++;
                }
            }
            if (count != k) {
                return -1;
            }
        }
        return ans;
    }

    public static int test(int[] arr, int k, int m) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }

    /**
     * 生成一个指定的数组，要求：数组中，有一个数出现k次，其他数出现m次，m>k>1
     * 
     * @param maxKinds 数的种类
     * @param range    数组取值范围
     * @param k        一种数出现了k次
     * @param m        其他数出现了m次
     * @return
     */
    public static int[] randomArry(int maxKinds, int range, int k, int m) {
        // 出现了k次的数
        int ktimeNum = randomNumber(range);
        // 题目变种， 当数组中存在出现k次的数时返回这个数,否则返回-1
        int times = Math.random() < 0.5 ? k : (int) (Math.random() * m);
        // 数的种类至少为两种
        int numKinds = (int) (Math.random() * maxKinds) + 2;
        // 数组中有 times*1 + (numKinds-1) * m 个数
        int[] arr = new int[times + (numKinds - 1) * m];
        int index = 0;
        for (; index < times; index++) {
            arr[index] = ktimeNum;
        }
        numKinds--;
        HashSet<Integer> set = new HashSet<>();
        set.add(ktimeNum);
        while (numKinds != 0) {
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            } while (set.contains(curNum));
            // 保证随机出来的数一定是新的
            set.add(curNum);
            numKinds--;
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
        }

        // 随机数组就生成好了，但是数据很有规律，需要打乱一下
        for (int i = 0; i < arr.length; i++) {
            // i 位置的数，随机和j位置的数做交换
            int j = (int) (Math.random() * arr.length); // 0 ～ N-1
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        return arr;
    }

    private static int randomNumber(int range) {
        return (int) (Math.random() * range) + 1 - ((int) (Math.random() * range));
    }

    public static void main(String[] args) {

        int kinds = 100;
        int range = 200;
        int testTime = 50000;
        int max = 9;
        System.out.println("测试开始！！");
        for (int i = 0; i < testTime; i++) {
            int a = (int) (Math.random() * max) + 1; // a 1 ~ 9
            int b = (int) (Math.random() * max) + 1; // b 1 ~ 9
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            // k < m
            if (k == m) {
                m++;
            }
            int[] arr = randomArry(kinds, range, k, m);
            int ans1 = test(arr, k, m);
            int ans2 = onlyKTimes(arr, k, m);
            if (ans1 != ans2) {
                System.out.println("出错了！！ k:" + k + ",m:" + m);
                // System.out.println(Arrays.toString(arr));
                // System.out.println(ans1);
                // System.out.println(ans2);
            }
        }
        System.out.println("测试结束！！");
    }
}
